package leetcode.code0218;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.TreeMap;

public class Solution extends Solution218 {

	@Override
	public List<List<Integer>> getSkyline(int[][] buildings) {
		int len = buildings.length;// 楼的数量len
		int wallNum = len << 1;// 墙的数量是 len * 2
		// int[i][0]第i面墙位置，int[i][1] 0:左墙 1:右墙 int[i][2] 墙高度
		int[][] walls = new int[wallNum][3];
		int pwall = 0; // 当前增加的墙的下标
		for (int i = 0; i < len; i++) {
			int height = buildings[i][2];// 楼高度，也是左墙和右墙的高度
			walls[pwall][0] = buildings[i][0];
			walls[pwall][1] = 0;// 左墙
			walls[pwall++][2] = height;
			walls[pwall][0] = buildings[i][1];
			walls[pwall][1] = 1;// 右墙
			walls[pwall++][2] = height;
		}
		Arrays.sort(walls, (o1, o2) -> {
			// 按照墙坐标从左到右，如果相同位置，先左墙，后右墙
			// 同一个位置，必须先加左墙，后减右墙，不然两个相连且等高的楼会被结算，本不应该结算的
			return o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0];
		});
		// 天花板高度
		TreeMap<Integer, Integer> ceiling = new TreeMap<>((o1, o2) -> o2 - o1);// 墙高h，当前视角叠了多少面高度为h的墙
		int H = -1;// 结算当前墙之前天花板的高度
		int P = -1;// 结算当前墙之前结算的位置
		// Map<Integer, Integer> ans = new LinkedHashMap<>();// 位置,天棚高度
		List<List<Integer>> ans = new ArrayList<>();
		for (int i = 0; i < wallNum; i++) {
			int[] wall = walls[i];
			int pos = wall[0];// 当前位置
			int type = wall[1];// 当前类型
			int h = wall[2];// 当前高度
			// 更新天棚高度
			if (type == 0) {// 左墙，增加可能的高度，是不是天棚交给ceiling去处理
				int num = ceiling.getOrDefault(h, 0);
				ceiling.put(h, num + 1);
			} else {// 右墙，减少可能的高度，会不会影响天棚，交给ceiling去处理
				int num = ceiling.get(h);
				if (num == 1) {// 最后一面高度为h的墙，说明高度为h的天棚没了。
					ceiling.remove(h);// 移除这个天棚
				} else {
					ceiling.put(h, num - 1);
				}
			}
			// 完成更新天棚高度后，开始结算这个位置的答案
			int cur = ceiling.isEmpty() ? 0 : ceiling.firstKey();// 当前位置的天花板高度
			if (cur != H) {// pos位置无论左墙右墙，pos的天花板的高度发生变化，这里就是答案中的一个
				if (pos != P && i != 0) {
					// 右墙逐渐撤走，天棚高度可能一直在变（也可能不变），最后一面墙撤走了的天棚高度才是最终确定
					// 所有P，H都是因为高度变化而产生的，都是备选答案，因为存在同一个位置高度下降的情况
					// 所以结算的时候，结算上一次的PH才能保证不重复。
					List<Integer> L = new ArrayList<>();
					L.add(P);
					L.add(H);
					ans.add(L);
				}
				P = pos;
				H = cur;
			}
		}
		// 结算最后一面墙的答案，一定是某一个位置的0高度
		List<Integer> L = new ArrayList<>();
		L.add(P);
		L.add(H);
		ans.add(L);
		return ans;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
	}

}
